/*
核心思路：排列完成后，遍历二维数组，获取多个一维数组，使用当前一维数组的最后一项与下一个一维数组的第一项进行对比

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。


示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
 

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
*/

class Solution {
    public static int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0]; // 处理空输入
        }

        // 1. 先修正每个区间的start和end（确保start <= end）
        for (int[] interval : intervals) {
            if (interval[0] > interval[1]) {
                // 交换start和end
                int temp = interval[0];
                interval[0] = interval[1];
                interval[1] = temp;
            }
        }

        // 2. 根据区间的start升序排序（start相同则按end升序）
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

        // 3. 合并区间
        List<int[]> result = new ArrayList<>();
        // 初始化当前合并区间为第一个区间
        int[] current = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            int currentEnd = current[1];
            int nextStart = intervals[i][0];
            int nextEnd = intervals[i][1];

            if (currentEnd >= nextStart) {
                // 有重叠，合并区间（取较大的end）
                current[1] = Math.max(currentEnd, nextEnd);
            } else {
                // 无重叠，添加当前区间到结果，更新current为下一个区间
                result.add(current);
                current = intervals[i];
            }
        }

        // 4. 添加最后一个合并的区间
        result.add(current);

        // 5. 转换为二维数组返回
        return result.toArray(new int[0][0]);
    }
}